import java.util.*;

public class Solution {

    private int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    private int[][] visited;
    private int res = 0;

    public boolean surpass(int x, int y, int threshold) {
        int sum = 0;

        while (x > 0) {
            sum += x % 10;
            x /= 10;
        }
        while (y > 0) {
            sum += y % 10;
            y /= 10;
        }

        
        return sum > threshold;
    }

    public void dfs(int x, int y, int threshold) {

        if (visited[x][y] == 1) {
            return ;
        }

        visited[x][y] = 1;

        if(surpass(x, y, threshold)) {
            return ;
        }

        res++;

        for (int i = 0; i < 4; i++) {
            int tempX = x + dir[i][0];
            int tempY = y + dir[i][1];

            if (0 <= tempX && tempX < visited.length && 0 <= tempY && tempY < visited[0].length) {
                dfs(tempX, tempY, threshold);
            }
        }


    }

    public int movingCount(int threshold, int rows, int cols) {
        visited = new int[rows][cols];

        dfs(0, 0, threshold);

        return res;
    }
}
